題目

https://leetcode.com/problems/flatten-binary-tree-to-linked-list/

Given a binary tree, flatten it to a linked list in-place.

For example, given the following tree:

Example:

    1
   / \
  2   5
/ \   \
3   4   6

The flattened tree should look like:

1
\
  2
   \
    3
     \
      4
       \
        5
         \
          6

解答

C#

/**
* Definition for a binary tree node.
* public class TreeNode {
*     public int val;
*     public TreeNode left;
*     public TreeNode right;
*     public TreeNode(int x) { val = x; }
* }
*/
public class Solution {
    public void Flatten(TreeNode root)
    {
        Flatten(root, null);
    }
    
    private TreeNode Flatten(TreeNode current, TreeNode cut)
    {
        if (current == null)
            return cut;
        cut = Flatten(current.right, cut);
        cut = Flatten(current.left, cut);
        current.right = cut;
        current.left = null;
        return current;
    }
}

結果

Runtime: 92 ms, faster than 97.29% of C# online submissions.

Memory Usage: 24 MB, less than 33.33% of C# online submissions.

Time Complexity: O(n)

Space Complextiy: O(1)

為什麼我要這樣做？

今天終於來到最後一題與 Tree 相關的演算法啦！還沒跟上的人記得往前複習 ↓
[Day 22] 演算法刷題 LeetCode 101. Symmetric Tree (Easy) Part 1 - Recursion
[Day 23] 演算法刷題 LeetCode 101. Symmetric Tree (Eas
y) Part 2 - Iteration
[Day 24] 演算法刷題 LeetCode 104. Maximum Depth of Binary Tree (Easy)
[Day 25] 演算法刷題 LeetCode 543. Diameter of Binary Tree (Easy)
[Day 26] 演算法刷題 LeetCode 226. Invert Binary Tree (Easy)
[Day 27] 演算法刷題 LeetCode 617. Merge Two Binary Trees (Easy)

1. 先實作 private 的 Faltten(TreeNode current, TreeNode ) 的 method
   • current 為要 接上去 的 node，cut 則是被 剪下來 的 node
   • 判斷若 current 為 null 時，回傳 cut
   • cut 則用遞迴的方式去巡覽，並找出要被剪下來的 cut node
   • 找到後，此時被要接上的 current.right = cut， current.left 則清空設為 null
   • 回傳 current ，並為下一輪遞迴做準備
2. 原本要實作的 Flatten(TreeNode root) 呼叫 private Flatten(root, null); 即可

示意圖

如果看文字敘述不是很明確的話，可以看下面的示意圖。

Step 1

Step 2

Step 3

以上就是這次 LeetCode 刷題的分享啦！
如果其它人有更棒的想法及意見，請留言或寄信(t4730@yahoo.com.tw) 給我。
那我們就下回見囉